package main

/*
Given a linked list, remove the n-th node from the end of list and return its head.

Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.
*/
type ListNode struct {
	val  int
	next *ListNode
}

func removeNodeFromEnd(head *ListNode, n int) *ListNode {
	var fast, slow *ListNode
	fast = head
	slow = head
	//先让快指针走n步
	for i := 0; i < n; i++ {
		fast = fast.next
	}
	if fast == nil {
		head = head.next
		return head
	}
	//慢指针和快指针隔n 前进，
	for fast.next != nil {
		fast = fast.next
		slow = slow.next
	}
	//跳过倒数n元素连接
	slow.next = slow.next.next
	return head
}
